#include "bstwindow.h"
#include <QPainter>
#include <QScrollArea>
#include <QDialog>
#include <QDialogButtonBox>
#include <QVBoxLayout>
#include <QFormLayout>
#include <QGridLayout>
#include <QTimer>

int BSTVisualizationWidget::getTreeHeight(BSTNode* node) const {
    if (node == nullptr) return 0;
    return 1 + max(getTreeHeight(node->left), getTreeHeight(node->right));
}

void BSTVisualizationWidget::paintEvent(QPaintEvent* event)
{
    Q_UNUSED(event);

    QPainter painter(this);
    painter.setRenderHint(QPainter::Antialiasing);
    painter.setPen(QPen(Qt::black, 2));

    QFont font = painter.font();
    font.setPointSize(10);
    painter.setFont(font);

    painter.fillRect(rect(), Qt::white);

    if (root == nullptr) {
        painter.drawText(rect(), Qt::AlignCenter, "二叉搜索树为空");
        return;
    }

    int height = getTreeHeight(root);

    drawTree(painter, root, width() / 2, 50, 1, height);

    // 显示当前可视化状态
    QString stateText;
    QColor stateColor;
    switch (visualizationState) {
    case VisualizationState::Insert:
        stateText = "插入节点中...";
        stateText += " [";
        switch (deleteSubState) { // 复用deleteSubState显示插入子状态
        case DeleteSubState::FindNode:
            stateText += "查找插入位置";
            break;
        case DeleteSubState::FindMaxInLeft:
            stateText += "显示新节点";
            break;
        case DeleteSubState::UpdatePointers:
            stateText += "创建连接";
            break;
        case DeleteSubState::ReplaceNode:
            stateText += "完成插入";
            break;
        default:
            break;
        }
        stateText += "]";
        stateColor = QColor(255, 165, 0); // 橙色
        break;
    case VisualizationState::Delete:
        stateText = "删除节点中...";
        stateText += " [";
        switch (deleteSubState) {
        case DeleteSubState::FindNode:
            stateText += "查找目标节点";
            break;
        case DeleteSubState::FindMaxInLeft:
            stateText += "在左子树中找最大节点";
            break;
        case DeleteSubState::UpdatePointers:
            stateText += "更新指针连接";
            break;
        case DeleteSubState::ReplaceNode:
            stateText += "替换节点";
            break;
        case DeleteSubState::DeleteOriginal:
            stateText += "删除原节点";
            break;
        case DeleteSubState::Complete:
            stateText += "完成删除";
            break;
        default:
            break;
        }
        stateText += "]";
        stateColor = QColor(220, 20, 60); // 红色
        break;
    case VisualizationState::Search:
        stateText = "查找节点中...";
        stateColor = QColor(0, 128, 0); // 绿色
        break;
    default:
        stateText = "就绪";
        stateColor = Qt::blue;
        break;
    }

    painter.setPen(stateColor);
    painter.drawText(10, 20, stateText);
}

void BSTVisualizationWidget::drawTree(QPainter& painter, BSTNode* node, int x, int y, int level, int maxLevel)
{
    if (node == nullptr) return;

    SimpleNodeMap pos;

    // 递归计算坐标
    struct Local {
        static void computePos(BSTNode* n, int cx, int cy, int lvl, SimpleNodeMap& positions, int widgetWidth) {
            if (!n) return;
            int shiftAmount = lvl + 1;
            if (shiftAmount > 8) shiftAmount = 8;
            int base = 40;
            if (widgetWidth / (1 << shiftAmount) > base) {
                base = widgetWidth / (1 << shiftAmount);
            }
            positions.insert(n, QPoint(cx, cy));
            int childY = cy + 70;
            if (n->left) {
                int childX = cx - base;
                computePos(n->left, childX, childY, lvl + 1, positions, widgetWidth);
            }
            if (n->right) {
                int childX = cx + base;
                computePos(n->right, childX, childY, lvl + 1, positions, widgetWidth);
            }
        }
    };

    Local::computePos(node, x, y, level, pos, width());

    // 如果存在新节点且处于插入状态，计算新节点的位置
    if (newNode && visualizationState == VisualizationState::Insert &&
        m_newNodeParent && (deleteSubState == DeleteSubState::FindMaxInLeft ||
                            deleteSubState == DeleteSubState::UpdatePointers ||
                            deleteSubState == DeleteSubState::Complete)) {
        QPoint parentPos;
        if (pos.find(m_newNodeParent, parentPos)) {
            int base = 40;
            int shiftAmount = level + 1;
            if (shiftAmount > 8) shiftAmount = 8;
            if (width() / (1 << shiftAmount) > base) {
                base = width() / (1 << shiftAmount);
            }

            int childY = parentPos.y() + 70;
            int childX = m_newNodeIsLeftChild ? parentPos.x() - base : parentPos.x() + base;
            m_newNodePosition = QPoint(childX, childY);
            pos.insert(newNode, m_newNodePosition);
        }
    }

    // 绘制所有边
    painter.setPen(QPen(Qt::black, 2));

    // 通过遍历树来绘制边
    struct EdgeDrawer {
        static void drawEdges(QPainter& painter, BSTNode* n, SimpleNodeMap& positions,
                              BSTNode* newNode, BSTNode* newNodeParent, bool newNodeIsLeftChild,
                              VisualizationState visualizationState, DeleteSubState deleteSubState,
                              BSTNode* replacementNode, BSTNode* deleteTarget,
                              BSTNode* maxInLeft, BSTNode* maxInLeftParent,
                              BSTNode* nodeToDelete) {
            if (!n) return;
            QPoint p;
            if (positions.find(n, p)) {
                // 绘制普通边
                if (n->left) {
                    QPoint c;
                    if (positions.find(n->left, c)) {
                        painter.drawLine(p.x(), p.y() + 15, c.x(), c.y() - 15);
                    }
                }
                if (n->right) {
                    QPoint c;
                    if (positions.find(n->right, c)) {
                        painter.drawLine(p.x(), p.y() + 15, c.x(), c.y() - 15);
                    }
                }

                // 如果处于创建连接阶段，绘制新节点的连接线
                if (visualizationState == VisualizationState::Insert &&
                    deleteSubState == DeleteSubState::UpdatePointers &&
                    newNode && newNodeParent == n) {
                    QPoint newNodePos;
                    if (positions.find(newNode, newNodePos)) {
                        // 使用虚线表示新连接
                        QPen dashedPen(Qt::red, 2, Qt::DashLine);
                        painter.setPen(dashedPen);
                        painter.drawLine(p.x(), p.y() + 15, newNodePos.x(), newNodePos.y() - 15);
                        painter.setPen(QPen(Qt::black, 2)); // 恢复普通画笔
                    }
                }

                // 在删除操作中显示指针更新
                if (visualizationState == VisualizationState::Delete &&
                    deleteSubState == DeleteSubState::UpdatePointers) {
                    // 如果当前节点是左子树最大节点，绘制到删除目标右子树的连接
                    if (maxInLeft && deleteTarget && deleteTarget->right && n == maxInLeft) {
                        QPoint rightChildPos;
                        if (positions.find(deleteTarget->right, rightChildPos)) {
                            // 使用绿色虚线表示新连接
                            QPen newConnectionPen(QColor(0, 150, 0), 2, Qt::DashLine);
                            painter.setPen(newConnectionPen);
                            painter.drawLine(p.x(), p.y() + 15, rightChildPos.x(), rightChildPos.y() - 15);
                            painter.setPen(QPen(Qt::black, 2)); // 恢复普通画笔
                        }
                    }
                }
            }
            drawEdges(painter, n->left, positions, newNode, newNodeParent, newNodeIsLeftChild,
                      visualizationState, deleteSubState, replacementNode, deleteTarget, maxInLeft, maxInLeftParent, nodeToDelete);
            drawEdges(painter, n->right, positions, newNode, newNodeParent, newNodeIsLeftChild,
                      visualizationState, deleteSubState, replacementNode, deleteTarget, maxInLeft, maxInLeftParent, nodeToDelete);
        }
    };

    EdgeDrawer::drawEdges(painter, node, pos, newNode, m_newNodeParent, m_newNodeIsLeftChild,
                          visualizationState, deleteSubState, replacementNode,
                          m_deleteTarget, m_maxInLeft, m_maxInLeftParent, m_nodeToDelete);

    // 绘制节点 - 同样通过遍历树
    struct NodeDrawer {
        static void drawNodes(QPainter& painter, BSTNode* n, SimpleNodeMap& positions,
                              BSTNode* currentVisited, BSTNode* targetNode,
                              BSTNode* newNode, BSTNode* replacementNode,
                              VisualizationState visualizationState, DeleteSubState deleteSubState,
                              BSTNode* deleteTarget, BSTNode* maxInLeft, BSTNode* nodeToDelete) {
            if (!n) return;

            QPoint p;
            if (positions.find(n, p)) {
                // 设置节点颜色
                QColor nodeColor = QColor(173, 216, 230);
                QColor textColor = Qt::black;
                int borderWidth = 2;
                QString nodeLabel = QString::number(n->data);

                if (n == currentVisited) {
                    // 当前正在访问的节点
                    switch (visualizationState) {
                    case VisualizationState::Insert:
                        nodeColor = QColor(255, 215, 0); // 金色
                        borderWidth = 4;
                        break;
                    case VisualizationState::Delete:
                        nodeColor = QColor(255, 99, 71); // 番茄红
                        borderWidth = 4;
                        if (deleteSubState == DeleteSubState::FindMaxInLeft) {
                            nodeLabel += "\n(查找中)";
                        }
                        break;
                    case VisualizationState::Search:
                        nodeColor = QColor(144, 238, 144); // 浅绿色
                        borderWidth = 4;
                        break;
                    default:
                        break;
                    }
                }

                if (n == targetNode) {
                    // 查找的目标节点或要删除的节点
                    nodeColor = QColor(220, 20, 60); // 红色
                    textColor = Qt::white;
                    borderWidth = 4;
                }

                if (n == newNode) {
                    // 新插入的节点
                    nodeColor = QColor(255, 165, 0); // 橙色
                    borderWidth = 4;

                    // 如果是新节点且处于创建连接阶段，添加特殊标记
                    if (visualizationState == VisualizationState::Insert) {
                        switch (deleteSubState) {
                        case DeleteSubState::FindMaxInLeft:
                            nodeLabel += "\n(新节点)";
                            break;
                        case DeleteSubState::UpdatePointers:
                            nodeLabel += "\n(连接中)";
                            break;
                        default:
                            break;
                        }
                    }
                }

                if (n == replacementNode) {
                    // 替换节点
                    nodeColor = QColor(50, 205, 50); // 绿色
                    textColor = Qt::white;
                    borderWidth = 4;
                    nodeLabel += "\n(替换节点)";
                }

                // 在删除操作中特殊标记关键节点
                if (visualizationState == VisualizationState::Delete) {
                    if (n == deleteTarget) {
                        nodeColor = QColor(220, 20, 60); // 红色
                        nodeLabel += "\n(删除目标)";
                    }
                    if (n == maxInLeft && deleteSubState == DeleteSubState::UpdatePointers) {
                        nodeColor = QColor(50, 205, 50); // 绿色
                        nodeLabel += "\n(最大节点)";
                    }
                }

                // 绘制节点
                painter.setBrush(QBrush(nodeColor));
                painter.setPen(QPen(Qt::black, borderWidth));
                painter.drawEllipse(p.x() - 20, p.y() - 20, 40, 40);

                painter.setPen(textColor);
                QFontMetrics fm(painter.font());
                QRect textRect = fm.boundingRect(nodeLabel);
                painter.drawText(p.x() - textRect.width()/2, p.y() + fm.height()/4, nodeLabel);
            }

            drawNodes(painter, n->left, positions, currentVisited, targetNode, newNode, replacementNode,
                      visualizationState, deleteSubState, deleteTarget, maxInLeft, nodeToDelete);
            drawNodes(painter, n->right, positions, currentVisited, targetNode, newNode, replacementNode,
                      visualizationState, deleteSubState, deleteTarget, maxInLeft, nodeToDelete);
        }
    };

    NodeDrawer::drawNodes(painter, node, pos, currentVisited, targetNode, newNode, replacementNode,
                          visualizationState, deleteSubState, m_deleteTarget, m_maxInLeft, m_nodeToDelete);

    // 如果新节点不在树中但需要显示，单独绘制
    if (newNode && visualizationState == VisualizationState::Insert &&
        (deleteSubState == DeleteSubState::FindMaxInLeft ||
         deleteSubState == DeleteSubState::UpdatePointers ||
         deleteSubState == DeleteSubState::Complete)) {
        QPoint p = m_newNodePosition;

        // 设置新节点颜色
        QColor nodeColor = QColor(255, 165, 0); // 橙色
        int borderWidth = 4;
        QString nodeLabel = QString::number(newNode->data);

        // 根据状态设置标签
        switch (deleteSubState) {
        case DeleteSubState::FindMaxInLeft:
            nodeLabel += "\n(新节点)";
            break;
        case DeleteSubState::UpdatePointers:
            nodeLabel += "\n(连接中)";
            break;
        default:
            break;
        }

        // 绘制新节点
        painter.setBrush(QBrush(nodeColor));
        painter.setPen(QPen(Qt::black, borderWidth));
        painter.drawEllipse(p.x() - 20, p.y() - 20, 40, 40);

        painter.setPen(Qt::black);
        QFontMetrics fm(painter.font());
        QRect textRect = fm.boundingRect(nodeLabel);
        painter.drawText(p.x() - textRect.width()/2, p.y() + fm.height()/4, nodeLabel);
    }
}


BSTWindow::BSTWindow(QWidget *parent)
    : QMainWindow(parent), m_root(nullptr), m_size(0),
    m_currentStepIndex(0), m_currentVisualization(VisualizationState::None),
    m_currentDeleteSubState(DeleteSubState::None),
    m_operationValue(-1), m_foundNode(nullptr), m_newNode(nullptr),
    m_replacementNode(nullptr), m_maxInLeft(nullptr), m_operationSuccess(false),
    m_random(QDateTime::currentMSecsSinceEpoch()),
    m_deleteTargetParent(nullptr), m_deleteTargetLeft(nullptr), m_deleteTargetRight(nullptr),
    m_maxInLeftParent(nullptr), m_maxInLeftIsRightChild(false),
    m_nodeToDelete(nullptr)
{
    setupUI();
    updateDisplay();

    // 初始化动画定时器
    m_animationTimer = new QTimer(this);
    m_animationTimer->setInterval(1200);
    connect(m_animationTimer, &QTimer::timeout, this, &BSTWindow::onVisualizationStep);
}

BSTWindow::~BSTWindow()
{
    clearTree(m_root);
}

void BSTWindow::setupUI()
{
    setWindowTitle("二叉搜索树可视化演示 - 增强删除操作");
    setMinimumSize(1400, 800);
    resize(1400, 800);

    QWidget *centralWidget = new QWidget(this);
    setCentralWidget(centralWidget);

    QHBoxLayout *mainLayout = new QHBoxLayout(centralWidget);

    // 左侧：可视化区域
    QVBoxLayout *leftLayout = new QVBoxLayout();
    leftLayout->setContentsMargins(10, 10, 10, 10);

    QLabel *visualLabel = new QLabel("二叉搜索树可视化:");
    visualLabel->setStyleSheet("font-weight: bold; font-size: 14px;");
    leftLayout->addWidget(visualLabel);

    // 创建滚动区域来容纳可视化部件
    m_scrollArea = new QScrollArea();
    m_scrollArea->setWidgetResizable(true);
    m_scrollArea->setHorizontalScrollBarPolicy(Qt::ScrollBarAsNeeded);
    m_scrollArea->setVerticalScrollBarPolicy(Qt::ScrollBarAsNeeded);
    m_scrollArea->setMinimumSize(800, 600);

    m_visualizationWidget = new BSTVisualizationWidget();
    m_visualizationWidget->setMinimumSize(1200, 800); // 设置足够大的最小尺寸以容纳树

    m_scrollArea->setWidget(m_visualizationWidget);
    leftLayout->addWidget(m_scrollArea);

    mainLayout->addLayout(leftLayout, 3); // 左侧占3/4空间

    // 右侧：操作和信息区域
    QVBoxLayout *rightLayout = new QVBoxLayout();
    rightLayout->setContentsMargins(5, 10, 5, 10);
    rightLayout->setSpacing(15);

    // 返回按钮
    QPushButton *returnBtn = new QPushButton("返回主菜单");
    returnBtn->setStyleSheet("QPushButton { background-color: #f0f0f0; border: 1px solid #ccc; padding: 8px; font-weight: bold; }");
    returnBtn->setFixedWidth(300);
    rightLayout->addWidget(returnBtn, 0, Qt::AlignHCenter);

    // 操作按钮区域
    QGroupBox *opsGroup = new QGroupBox("操作面板");
    opsGroup->setStyleSheet("QGroupBox { font-weight: bold; }");
    opsGroup->setFixedWidth(300);

    QGridLayout *opsLayout = new QGridLayout(opsGroup);
    opsLayout->setVerticalSpacing(10);
    opsLayout->setHorizontalSpacing(10);

    // 第一行按钮
    QPushButton *inputBtn = new QPushButton("构建BST");
    inputBtn->setMinimumHeight(35);
    opsLayout->addWidget(inputBtn, 0, 0);

    QPushButton *insertBtn = new QPushButton("插入节点");
    insertBtn->setMinimumHeight(35);
    opsLayout->addWidget(insertBtn, 0, 1);

    // 第二行按钮
    QPushButton *deleteBtn = new QPushButton("删除节点");
    deleteBtn->setMinimumHeight(35);
    opsLayout->addWidget(deleteBtn, 1, 0);

    QPushButton *searchBtn = new QPushButton("查找节点");
    searchBtn->setMinimumHeight(35);
    opsLayout->addWidget(searchBtn, 1, 1);

    // 第三行按钮
    QPushButton *clearBtn = new QPushButton("清空BST");
    clearBtn->setMinimumHeight(35);
    opsLayout->addWidget(clearBtn, 2, 0);

    QPushButton *randomBtn = new QPushButton("生成随机BST");
    randomBtn->setMinimumHeight(35);
    opsLayout->addWidget(randomBtn, 2, 1);

    rightLayout->addWidget(opsGroup, 0, Qt::AlignHCenter);

    // 信息显示区域
    QGroupBox *infoGroup = new QGroupBox("二叉搜索树信息");
    infoGroup->setStyleSheet("QGroupBox { font-weight: bold; }");
    infoGroup->setFixedWidth(300);
    QVBoxLayout *infoLayout = new QVBoxLayout(infoGroup);

    m_display = new QTextEdit();
    m_display->setReadOnly(true);
    m_display->setMinimumHeight(400);
    m_display->setStyleSheet("QTextEdit { background-color: #f8f8f8; border: 1px solid #ddd; padding: 5px; }");
    infoLayout->addWidget(m_display);

    rightLayout->addWidget(infoGroup);
    rightLayout->addStretch(1);

    mainLayout->addLayout(rightLayout, 1);

    // 连接信号槽
    connect(inputBtn, &QPushButton::clicked, this, &BSTWindow::onInputData);
    connect(insertBtn, &QPushButton::clicked, this, &BSTWindow::onInsert);
    connect(deleteBtn, &QPushButton::clicked, this, &BSTWindow::onDelete);
    connect(searchBtn, &QPushButton::clicked, this, &BSTWindow::onSearch);
    connect(clearBtn, &QPushButton::clicked, this, &BSTWindow::onClear);
    connect(randomBtn, &QPushButton::clicked, this, &BSTWindow::onGenerateRandom);
    connect(returnBtn, &QPushButton::clicked, this, &BSTWindow::onReturnToMainMenu);
}

void BSTWindow::onReturnToMainMenu()
{
    emit returnToMainMenu();
    this->close();
}

QString BSTWindow::getInputDialog(const QString& title, const QString& label, const QString& placeholder)
{
    QDialog dialog(this);
    dialog.setWindowTitle(title);

    QVBoxLayout *layout = new QVBoxLayout(&dialog);

    QLabel *promptLabel = new QLabel(label);
    QLineEdit *lineEdit = new QLineEdit();
    lineEdit->setPlaceholderText(placeholder);

    QDialogButtonBox *buttonBox = new QDialogButtonBox(QDialogButtonBox::Ok | QDialogButtonBox::Cancel);

    layout->addWidget(promptLabel);
    layout->addWidget(lineEdit);
    layout->addWidget(buttonBox);

    connect(buttonBox, &QDialogButtonBox::accepted, &dialog, &QDialog::accept);
    connect(buttonBox, &QDialogButtonBox::rejected, &dialog, &QDialog::reject);

    if (dialog.exec() == QDialog::Accepted) {
        return lineEdit->text();
    }

    return QString();
}

int BSTWindow::getIntegerInputDialog(const QString& title, const QString& label, bool* ok)
{
    QDialog dialog(this);
    dialog.setWindowTitle(title);

    QVBoxLayout *layout = new QVBoxLayout(&dialog);

    QLabel *promptLabel = new QLabel(label);
    QLineEdit *lineEdit = new QLineEdit();

    QDialogButtonBox *buttonBox = new QDialogButtonBox(QDialogButtonBox::Ok | QDialogButtonBox::Cancel);

    layout->addWidget(promptLabel);
    layout->addWidget(lineEdit);
    layout->addWidget(buttonBox);

    connect(buttonBox, &QDialogButtonBox::accepted, &dialog, &QDialog::accept);
    connect(buttonBox, &QDialogButtonBox::rejected, &dialog, &QDialog::reject);

    if (dialog.exec() == QDialog::Accepted) {
        return lineEdit->text().toInt(ok);
    }

    if (ok) *ok = false;
    return 0;
}

void BSTWindow::updateDisplay()
{
    QString info = QString("节点数量: %1\n\n").arg(m_size);

    if (m_root == nullptr) {
        info += "二叉搜索树为空";
    } else {
        info += "中序遍历: ";
        QString inorder;
        inorderTraversal(m_root, inorder);
        info += inorder + "\n\n";

        info += QString("树的高度: %1").arg(getTreeHeight(m_root));
    }

    m_display->setText(info);
    m_visualizationWidget->setRoot(m_root);
    m_visualizationWidget->update();
}

void BSTWindow::clearTree(BSTNode* node)
{
    if (node == nullptr) return;
    clearTree(node->left);
    clearTree(node->right);
    delete node;
}

BSTNode* BSTWindow::insertNode(BSTNode* node, int value, BSTNode* parent)
{
    if (node == nullptr) {
        m_size++;
        return new BSTNode(value, parent);
    }

    if (value < node->data) {
        node->left = insertNode(node->left, value, node);
    } else if (value > node->data) {
        node->right = insertNode(node->right, value, node);
    }

    return node;
}

BSTNode* BSTWindow::deleteNode(BSTNode* node, int value)
{
    if (node == nullptr) return nullptr;

    if (value < node->data) {
        node->left = deleteNode(node->left, value);
    } else if (value > node->data) {
        node->right = deleteNode(node->right, value);
    } else {
        if (node->left == nullptr) {
            BSTNode* temp = node->right;
            if (temp) temp->parent = node->parent;
            delete node;
            m_size--;
            return temp;
        } else if (node->right == nullptr) {
            BSTNode* temp = node->left;
            if (temp) temp->parent = node->parent;
            delete node;
            m_size--;
            return temp;
        }

        // 既有左子树又有右子树的情况
        BSTNode* temp = findMax(node->left); // 在左子树中找最大节点
        node->data = temp->data;
        node->left = deleteNode(node->left, temp->data);
    }

    return node;
}

BSTNode* BSTWindow::findMin(BSTNode* node)
{
    while (node != nullptr && node->left != nullptr) {
        node = node->left;
    }
    return node;
}

BSTNode* BSTWindow::findMax(BSTNode* node)
{
    while (node != nullptr && node->right != nullptr) {
        node = node->right;
    }
    return node;
}

bool BSTWindow::searchNode(BSTNode* node, int value)
{
    if (node == nullptr) return false;

    if (value == node->data) return true;
    else if (value < node->data) return searchNode(node->left, value);
    else return searchNode(node->right, value);
}

void BSTWindow::inorderTraversal(BSTNode* node, QString& result)
{
    if (node == nullptr) return;
    inorderTraversal(node->left, result);
    result += QString::number(node->data) + " ";
    inorderTraversal(node->right, result);
}

BSTNode* BSTWindow::buildBSTFromValues(const IntVector& values)
{
    BSTNode* root = nullptr;
    for (int i = 0; i < values.size(); i++) {
        root = insertNode(root, values[i]);
    }
    return root;
}

int BSTWindow::getTreeHeight(BSTNode* node)
{
    if (node == nullptr) return 0;
    return 1 + max(getTreeHeight(node->left), getTreeHeight(node->right));
}

// 随机数生成函数 - 参考二叉树代码
int BSTWindow::randomInt(int min, int max)
{
    return m_random.nextInt(min, max);
}

// 可视化操作函数
void BSTWindow::startInsertVisualization(int value)
{
    m_operationPath.clear();
    m_currentStepIndex = 0;
    m_currentVisualization = VisualizationState::Insert;
    m_operationValue = value;
    m_operationSuccess = false;
    m_newNode = nullptr;

    // 模拟插入路径
    BSTNode* current = m_root;
    BSTNode* parent = nullptr;
    bool isLeftChild = false; // 记录新节点应该是左孩子还是右孩子

    while (current != nullptr) {
        m_operationPath.push_back(current);
        if (value == current->data) {
            // 值已存在，不插入
            m_operationSuccess = false;
            break;
        } else if (value < current->data) {
            parent = current;
            current = current->left;
            isLeftChild = true;
        } else {
            parent = current;
            current = current->right;
            isLeftChild = false;
        }
    }

    // 如果值不存在，创建新节点
    if (current == nullptr) {
        m_newNode = new BSTNode(value, parent);
        m_operationSuccess = true;

        // 设置可视化部件的新节点位置信息
        m_visualizationWidget->setNewNodePositionInfo(parent, isLeftChild);
    }

    m_visualizationWidget->setVisualizationState(VisualizationState::Insert);
    m_visualizationWidget->setDeleteSubState(DeleteSubState::FindNode); // 复用DeleteSubState显示插入状态
    m_visualizationWidget->setNewNode(m_newNode); // 设置新节点
    m_animationTimer->start();
}

void BSTWindow::startDeleteVisualization(int value)
{
    m_operationPath.clear();
    m_currentStepIndex = 0;
    m_currentVisualization = VisualizationState::Delete;
    m_currentDeleteSubState = DeleteSubState::FindNode;
    m_operationValue = value;
    m_operationSuccess = false;
    m_foundNode = nullptr;
    m_replacementNode = nullptr;
    m_maxInLeft = nullptr;

    // 重置指针跟踪变量
    m_deleteTargetParent = nullptr;
    m_deleteTargetLeft = nullptr;
    m_deleteTargetRight = nullptr;
    m_maxInLeftParent = nullptr;
    m_maxInLeftIsRightChild = false;
    m_nodeToDelete = nullptr;

    // 模拟删除查找路径
    BSTNode* current = m_root;

    while (current != nullptr) {
        m_operationPath.push_back(current);
        if (value == current->data) {
            m_foundNode = current;
            m_operationSuccess = true;

            // 记录要删除节点的信息
            m_deleteTargetParent = current->parent;
            m_deleteTargetLeft = current->left;
            m_deleteTargetRight = current->right;
            break;
        } else if (value < current->data) {
            current = current->left;
        } else {
            current = current->right;
        }
    }

    m_visualizationWidget->setVisualizationState(VisualizationState::Delete);
    m_visualizationWidget->setDeleteSubState(DeleteSubState::FindNode);
    m_animationTimer->start();
}

void BSTWindow::startSearchVisualization(int value)
{
    m_operationPath.clear();
    m_currentStepIndex = 0;
    m_currentVisualization = VisualizationState::Search;
    m_operationValue = value;
    m_operationSuccess = false;
    m_foundNode = nullptr;

    // 模拟查找路径
    BSTNode* current = m_root;

    while (current != nullptr) {
        m_operationPath.push_back(current);
        if (value == current->data) {
            m_foundNode = current;
            m_operationSuccess = true;
            break;
        } else if (value < current->data) {
            current = current->left;
        } else {
            current = current->right;
        }
    }

    m_visualizationWidget->setVisualizationState(VisualizationState::Search);
    m_animationTimer->start();
}

void BSTWindow::onVisualizationStep()
{
    if (m_currentVisualization == VisualizationState::Delete) {
        handleDeleteVisualizationStep();
    } else {
        handleStandardVisualizationStep();
    }
}

void BSTWindow::handleStandardVisualizationStep()
{
    if (m_currentVisualization == VisualizationState::Insert) {
        handleInsertVisualizationStep();
    } else if (m_currentVisualization == VisualizationState::Search) {
        handleSearchVisualizationStep();
    }
}

// 处理插入可视化步骤
void BSTWindow::handleInsertVisualizationStep()
{
    // 查找插入位置阶段
    if (m_currentStepIndex < m_operationPath.size()) {
        BSTNode* currentNode = m_operationPath[m_currentStepIndex];
        m_visualizationWidget->setCurrentVisited(currentNode);
        m_currentStepIndex++;
    } else {
        // 查找插入位置完成
        if (m_operationSuccess && m_newNode) {
            // 停止动画定时器，避免与后续的单次定时器冲突
            m_animationTimer->stop();

            // 进入显示新节点阶段
            m_visualizationWidget->setDeleteSubState(DeleteSubState::FindMaxInLeft); // 复用状态显示
            m_visualizationWidget->setNewNode(m_newNode);
            m_visualizationWidget->setCurrentVisited(nullptr);

            // 增加延迟时间
            QTimer::singleShot(1200, this, [this]() {
                m_visualizationWidget->setDeleteSubState(DeleteSubState::UpdatePointers); // 复用状态显示

                // 增加延迟时间
                QTimer::singleShot(800, this, [this]() {
                    // 直接完成插入，不再次触发定时器
                    onVisualizationFinished();
                });
            });
        } else {
            onVisualizationFinished();
        }
    }
}

// 处理查找可视化步骤
void BSTWindow::handleSearchVisualizationStep()
{
    if (m_currentStepIndex < m_operationPath.size()) {
        BSTNode* currentNode = m_operationPath[m_currentStepIndex];
        m_visualizationWidget->setCurrentVisited(currentNode);
        m_currentStepIndex++;
    } else {
        // 所有路径节点已显示，显示最终结果
        if (m_operationSuccess && m_foundNode) {
            m_visualizationWidget->setTargetNode(m_foundNode);
            // 增加延迟时间
            QTimer::singleShot(800, this, &BSTWindow::onVisualizationFinished);
            return;
        }
        onVisualizationFinished();
    }
}

void BSTWindow::handleDeleteVisualizationStep()
{
    switch (m_currentDeleteSubState) {
    case DeleteSubState::FindNode:
        if (m_currentStepIndex < m_operationPath.size()) {
            BSTNode* currentNode = m_operationPath[m_currentStepIndex];
            m_visualizationWidget->setCurrentVisited(currentNode);
            m_currentStepIndex++;
        } else {
            // 查找目标节点完成
            if (m_operationSuccess && m_foundNode) {
                m_visualizationWidget->setTargetNode(m_foundNode);
                m_visualizationWidget->setCurrentVisited(m_foundNode);

                // 判断节点类型
                if (m_foundNode->left && m_foundNode->right) {
                    // 既有左子树又有右子树，进入查找左子树最大节点阶段
                    m_currentDeleteSubState = DeleteSubState::FindMaxInLeft;
                    m_visualizationWidget->setDeleteSubState(DeleteSubState::FindMaxInLeft);

                    // 清空路径，开始查找左子树最大节点
                    m_operationPath.clear();
                    m_currentStepIndex = 0;

                    BSTNode* current = m_foundNode->left;
                    BSTNode* parent = m_foundNode; // 记录父节点
                    bool isRightChild = false;

                    while (current != nullptr) {
                        m_operationPath.push_back(current);
                        if (current->right == nullptr) {
                            m_maxInLeft = current;
                            m_maxInLeftParent = parent;
                            m_maxInLeftIsRightChild = isRightChild;
                            break;
                        }
                        parent = current;
                        current = current->right;
                        isRightChild = true;
                    }
                } else {
                    // 直接删除的情况
                    m_currentDeleteSubState = DeleteSubState::Complete;
                    m_visualizationWidget->setDeleteSubState(DeleteSubState::Complete);
                    // 增加延迟时间
                    QTimer::singleShot(800, this, &BSTWindow::onVisualizationFinished);
                }
            } else {
                onVisualizationFinished();
            }
        }
        break;

    case DeleteSubState::FindMaxInLeft:
        if (m_currentStepIndex < m_operationPath.size()) {
            BSTNode* currentNode = m_operationPath[m_currentStepIndex];
            m_visualizationWidget->setCurrentVisited(currentNode);
            m_currentStepIndex++;
        } else {
            // 找到左子树最大节点
            if (m_maxInLeft) {
                m_visualizationWidget->setReplacementNode(m_maxInLeft);
                m_visualizationWidget->setCurrentVisited(m_maxInLeft);

                // 设置删除操作中的关键节点
                m_visualizationWidget->setDeleteNodes(m_foundNode, m_maxInLeft, m_maxInLeftParent);

                // 进入更新指针阶段 - 将r的右指针指向p的右子树
                m_currentDeleteSubState = DeleteSubState::UpdatePointers;
                m_visualizationWidget->setDeleteSubState(DeleteSubState::UpdatePointers);

                // 增加延迟时间
                QTimer::singleShot(1200, this, [this]() {
                    // 直接完成删除
                    m_currentDeleteSubState = DeleteSubState::Complete;
                    m_visualizationWidget->setDeleteSubState(DeleteSubState::Complete);
                    // 增加延迟时间
                    QTimer::singleShot(800, this, &BSTWindow::onVisualizationFinished);
                });
            } else {
                onVisualizationFinished();
            }
        }
        break;

    default:
        break;
    }
}

void BSTWindow::onVisualizationFinished()
{
    // 停止动画定时器
    m_animationTimer->stop();

    QString result;
    bool success = false;

    switch (m_currentVisualization) {
    case VisualizationState::Insert:
        if (m_operationSuccess) {
            // 实际执行插入
            m_root = insertNode(m_root, m_operationValue);
            updateDisplay();

            // 显示插入流程详情
            QString detailedResult = QString("插入完成！节点 %1 已成功插入\n\n").arg(m_operationValue);
            detailedResult += "插入流程详情：\n";
            detailedResult += "1. 查找插入位置\n";
            detailedResult += "2. 创建新节点\n";
            detailedResult += "3. 建立父子节点连接\n";
            detailedResult += "4. 插入完成";
            result = detailedResult;
            success = true;

            // 插入成功后，新节点已经成为树的一部分，不再需要单独显示
            m_newNode = nullptr;
            m_visualizationWidget->setNewNode(nullptr);
        } else {
            result = QString("插入失败！节点 %1 已存在").arg(m_operationValue);
        }
        break;

    case VisualizationState::Delete:
        if (m_operationSuccess) {
            // 实际执行删除
            if (m_foundNode->left && m_foundNode->right) {
                // 对于有两个子节点的情况，我们手动执行删除过程以便更好地控制

                // 保存要删除节点的数据
                int deleteValue = m_foundNode->data;

                // 实际执行删除操作
                m_root = deleteNode(m_root, m_operationValue);

                QString detailedResult = QString("删除完成！节点 %1 已成功删除\n\n").arg(m_operationValue);
                detailedResult += "删除流程详情：\n";
                detailedResult += "1. 找到目标节点\n";
                detailedResult += QString("2. 在左子树中找到最大节点 %1\n").arg(m_maxInLeft ? m_maxInLeft->data : 0);
                detailedResult += "3. 将最大节点的右指针指向目标节点的右子树\n";
                detailedResult += "4. 用目标节点的左子树根节点替换目标节点";
                result = detailedResult;
            } else {
                // 对于只有一个或零个子节点的情况，使用原来的删除方法
                m_root = deleteNode(m_root, m_operationValue);
                result = QString("删除完成！节点 %1 已成功删除").arg(m_operationValue);
            }

            updateDisplay();
            success = true;
        } else {
            result = QString("删除失败！节点 %1 不存在").arg(m_operationValue);
        }
        break;

    case VisualizationState::Search:
        if (m_operationSuccess) {
            result = QString("查找完成！节点 %1 存在").arg(m_operationValue);
            success = true;
        } else {
            result = QString("查找完成！节点 %1 不存在").arg(m_operationValue);
        }
        break;

    default:
        break;
    }

    // 清理资源
    if (m_newNode && !success) {
        delete m_newNode;
        m_newNode = nullptr;
        m_visualizationWidget->setNewNode(nullptr);
    }

    // 清理删除相关的临时变量
    m_deleteTargetParent = nullptr;
    m_deleteTargetLeft = nullptr;
    m_deleteTargetRight = nullptr;
    m_maxInLeftParent = nullptr;
    m_nodeToDelete = nullptr;

    QMessageBox::information(this, "操作完成", result);

    // 重置可视化状态
    m_visualizationWidget->resetVisualization();
    m_currentVisualization = VisualizationState::None;
    m_currentDeleteSubState = DeleteSubState::None;
}

void BSTWindow::onInputData()
{
    QString input = getInputDialog("构建BST", "输入元素，用空格分隔:", "5 3 7 2 4 6 8");
    if (input.isEmpty()) {
        return; // 用户取消输入
    }

    clearTree(m_root);
    m_root = nullptr;
    m_size = 0;

    // 手动分割字符串
    IntVector values;
    const QChar* str = input.constData();
    int length = input.length();
    int start = 0;

    for (int i = 0; i <= length; i++) {
        if (i == length || str[i] == ' ') {
            if (start < i) {
                QString numStr = input.mid(start, i - start);
                bool ok;
                int value = numStr.toInt(&ok);
                if (ok) {
                    values.push_back(value);
                } else {
                    QMessageBox::warning(this, "输入错误", QString("'%1' 不是有效的整数").arg(numStr));
                    return;
                }
            }
            start = i + 1;
        }
    }

    if (values.size() > 0) {
        m_root = buildBSTFromValues(values);
        updateDisplay();
        QMessageBox::information(this, "构建成功", QString("已构建包含 %1 个节点的BST").arg(values.size()));
    }
}

void BSTWindow::onInsert()
{
    bool ok;
    int value = getIntegerInputDialog("插入节点", "请输入要插入的值:", &ok);

    if (!ok) {
        return; // 用户取消输入或输入无效
    }

    if (m_root == nullptr) {
        // 树为空，直接插入
        m_root = new BSTNode(value);
        m_size++;
        updateDisplay();
        QMessageBox::information(this, "插入成功", QString("节点 %1 已插入").arg(value));
    } else {
        startInsertVisualization(value);
    }
}

void BSTWindow::onDelete()
{
    bool ok;
    int value = getIntegerInputDialog("删除节点", "请输入要删除的值:", &ok);

    if (!ok) {
        return; // 用户取消输入或输入无效
    }

    if (m_root == nullptr) {
        QMessageBox::information(this, "删除失败", "二叉搜索树为空");
        return;
    }

    startDeleteVisualization(value);
}

void BSTWindow::onSearch()
{
    bool ok;
    int value = getIntegerInputDialog("查找节点", "请输入要查找的值:", &ok);

    if (!ok) {
        return; // 用户取消输入或输入无效
    }

    if (m_root == nullptr) {
        QMessageBox::information(this, "查找结果", "二叉搜索树为空");
        return;
    }

    startSearchVisualization(value);
}

void BSTWindow::onClear()
{
    if (m_root == nullptr) {
        QMessageBox::information(this, "清空", "二叉搜索树已为空");
        return;
    }

    clearTree(m_root);
    m_root = nullptr;
    m_size = 0;
    updateDisplay();
    QMessageBox::information(this, "清空成功", "二叉搜索树已清空");
}

void BSTWindow::onGenerateRandom()
{
    clearTree(m_root);
    m_root = nullptr;
    m_size = 0;

    // 参考二叉树代码的随机生成逻辑
    int nodeCount = randomInt(5, 8); // 生成5-8个节点
    IntVector values;

    // 生成不重复的随机值
    for (int i = 0; i < nodeCount; i++) {
        int value;
        bool duplicate;

        do {
            duplicate = false;
            value = randomInt(1, 99); // 1-99之间的随机数

            // 检查是否重复
            for (int j = 0; j < values.size(); j++) {
                if (values[j] == value) {
                    duplicate = true;
                    break;
                }
            }
        } while (duplicate);

        values.push_back(value);
    }

    // 构建BST
    m_root = buildBSTFromValues(values);
    updateDisplay();

    // 显示详细信息
    QString inorder;
    inorderTraversal(m_root, inorder);
    QMessageBox::information(this, "生成成功",
                             QString("已生成包含 %1 个节点的随机BST\n\n中序遍历结果:\n%2")
                                 .arg(nodeCount)
                                 .arg(inorder));
}
